/**
* @description: 790. 多米诺和托米诺平铺
* @author hewei
* @date 2022/8/27 15:06
* @version 1.0
*/

public class NumTilings {

    public static void main(String[] args) {
        NumTilings numTilings = new NumTilings();
        System.out.println(numTilings.numTilings(40));
    }

    public int numTilings1(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        long res = 0;
        res += numTilings1(n - 1);
        res += numTilings1(n - 2);
        for (int i = n - 3; i >= 0; i--) {
            res += numTilings1(i) * 2L;
        }
        return (int) (res % (10e9 + 7));
    }

    public int numTilings2(int n) {
        int mod = (int) (1e9 + 7);
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        if (n > 1) dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            long res = dp[i - 1] + dp[i - 2];
            for (int j = 0; j <= i - 3; j++) {
                res += (dp[j] * 2L) % mod;
            }
            dp[i] = (int) (res % mod);
        }
        return dp[n] % mod;
    }

    public int numTilings(int n) {
        int mod = (int) (1e9 + 7);
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        if (n > 1) dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = (int) ((dp[i - 3] + dp[i - 1] * 2L) % mod);
        }
        return dp[n];
    }
}